package com.leetcode.array;

/**
 * Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]  =2
 * @author Adiy
 *
 */
public class UniquePathsII {

	public static void main(String[] args) {
		
		int grid[][]={
				{0,1,0,0,0},
				{0,0,0,1,0},
				{0,0,0,1,0},
				{1,1,0,0,1},
				{1,0,0,0,1},
				{0,1,0,0,0}
		};
		int result=uniquePathsWithObstacles(grid);
		System.out.println(result);
	}
	public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
	    
	    int lenr=obstacleGrid.length;
	    int lenc=obstacleGrid[0].length;
	    if(obstacleGrid[0][0]==1||obstacleGrid[lenr-1][lenc-1]==1) return 0;  
	    int[][] uniquePaths=new int[lenr][lenc];
	    int i=0,j=0;
	    for(i=0;i<lenc;i++){
	    	if(obstacleGrid[0][i]==1){
	    		break;
	    	}else 
	    		uniquePaths[0][i]=1;
	    	
	    }
//	    int kc=i;
//	    while(kc<lenc){
//	    	uniquePaths[0][kc]=0;
//	    	kc++;
//	    }
	    ///////////////////
	    for(j=0;j<lenr;j++){
	    	if(obstacleGrid[j][0]==1){
	    		break;
	    	}else 
	    		uniquePaths[j][0]=1;
	    	
	    }
//	    int kr=j;
//	    while(kr<lenr){
//	    	uniquePaths[kr][0]=0;
//	    	kr++;
//	    }
	    
	    for(int ii=1;ii<lenr;ii++)
	    	for(int jj=1;jj<lenc;jj++){
	    		if(obstacleGrid[ii][jj]==0)
	    			uniquePaths[ii][jj]=uniquePaths[ii-1][jj]+uniquePaths[ii][jj-1];
	    		else
	    			uniquePaths[ii][jj]=0;
	    	}
	    return uniquePaths[lenr-1][lenc-1];
	}
	
}
